#pragma once
#include <iostream>
#include <string.h>

using std::cout;
using std::endl;

class Bitmap{
public:
    Bitmap(): max_(1000), arr_(new char[max_ / 8 + 1])
    {
        memset(arr_, 0, (max_ / 8 + 1) * sizeof(char));
    }
    ~Bitmap()
    {
        delete []arr_;
    }

    void add(int val)
    {
        if(val > max_)
            expand(val);

        int idx = val / 8;
        int mod = val % 8;

        arr_[idx] = arr_[idx] | (1 << mod);
    } 

    bool contain(int val) const
    {
        if(val > max_) return false;
        int idx = val / 8;
        int mod = val % 8;
       
        return (arr_[idx] & (1 << mod)) == (1 << mod);
    }

private:
    void expand(int val)
    {
        char *tmp = new char[val / 8 + 1];
        memcpy(tmp, arr_, (max_ / 8 + 1) * sizeof(char));
        
        delete []arr_;
        arr_ = tmp;
        max_ = val;
    }

private:
    char *arr_;
    int max_;
};

/* void test1()
{
    Bitmap bit;
    bit.add(0);
    cout << std::boolalpha;
    cout << bit.contain(0) << endl;
    cout << bit.contain(1) << endl;
    bit.add(1);
    cout << bit.contain(1) << endl;
    bit.add(10000);
    cout << bit.contain(10001) << endl;
    cout << bit.contain(10000) << endl;
} */

// int main(int args, char *argv[])
// {
//     test1();
//     return 0;
// }